#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <time.h>

#define NR_TOTAL 20
#define NR_CPU 2
#define NR_CHILD (NR_TOTAL / NR_CPU)

struct param {
	int *array;
	int start;
	int end;
};

void *sort(void *arg)
{
	struct param *param;
	int i, j, temp;

	param = (struct param *)arg;
	for (i = param->start; i < param->end; ++i) {
		int max = param->array[i];
		int t = i;
		for (j = i + 1; j < param->end; ++j) {
	       		if (max < param->array[j]) {
				max = param->array[j];
				t = j;
			}

		}
		if (t != i) {
			temp = param->array[i];
			param->array[i] = param->array[t];
			param->array[t] = temp;
		}
	}

}

void print_array(int *array)
{
	int i;
	for (i = 0; i < NR_TOTAL; ++i)
		printf("%d ",array[i]);
	printf("\n");
}

void Merge(int *array)
{
	int *new_array = malloc(sizeof(int) * NR_TOTAL);
	int i = 0, j = NR_CHILD, k = 0;

	while (i < NR_CHILD && j <NR_TOTAL) {
		if (array[i] < array[j]) 
			new_array[k++] = array[j++];
		else
			new_array[k++] = array[i++];
	}
	while (i < NR_CHILD)
		new_array[k++] = array[i++];
	while (j < NR_TOTAL)
		new_array[k++] = array[j++];

	print_array(new_array);
	free(new_array);
}

int main()
{
	pthread_t workers[NR_CPU];
	struct param params[NR_CPU];
	int i;

	int *array = malloc(sizeof(int) * NR_TOTAL);
	srand(time(NULL));
	for (i = 0; i < NR_TOTAL; ++i) {
		array[i] = rand() % 100;
	}

	printf("Before Sort :");
	print_array(array);

	for (i = 0; i < NR_CPU; ++i) {
		struct param *param;
		param = &params[i];
		param->array = array;
		param->start = i * NR_CHILD;
		param->end = (i + 1) * NR_CHILD;
		pthread_create(&workers[i], NULL, sort, param);
	}

	for (i = 0; i < NR_CPU; ++i) 
        	pthread_join(workers[i], NULL);

	printf("After Sort :");
	Merge(array);
	free(array);
	return 0;
}
